As the world population increases, more and more infrastructure, buildings, exterior and interior development, and other features to support human growth are being generated. Also, existing, infrastructure, buildings, parks, and other environments are being adapted to accommodate more people and traffic. The increase and adaptation of environments impacts travel and how people go from one place to another.
Navigation systems and/or devices are used to aid travel. For example, vehicle navigation devices may assist a person driving on a road network. Such devices may provide routing and guidance to a desired destination based on existing roads or pathways.
There are areas, however, in which people move about that do not have set roads, tracks, or paths or in which such paths are not needed to travel from one point to another within the area. For example, floors of a building, parks, or other exterior or interior areas are treaded upon on a daily basis. People are able to move about in such areas in any number of patterns to get from one place to another. Some movement or patterns of movement in these areas may be inefficient or unnecessary based on confusion, lack of knowledge of the layout of an area, or other factors. Also, a person may not know how to get from one point to a desired destination in such areas.
In certain examples, certain routes may be generated from a navigation mesh. Such routes directly generated from navigation meshes may not be smooth or may be more complex than necessary. Additionally, artifacts from the mesh layout may produce jagged or undesirable looking routes. These navigation mesh routes may also be difficult to provide turn-by-turn guidance, as it may not be apparent where the turns occur.
In certain embodiments, a technique referred to as a “string-pulling” algorithm or “pull-on-string” algorithm may be applied to simplify the route and make it more direct. This string-pulling algorithm includes a process of starting at one end of the route and checking whether intermediate points can be removed without violating the navigation mesh.
One problem with the string-pulling algorithm is that the algorithm does not respect the original shape of the route. In other words, it is a greedy algorithm that is only concerned with shortening the route. As such, the string-pulling algorithm may result in strange or unnatural looking routes that do not resemble the original route well.